package com.zhzh.sc.demo.leetcode.learn.link;

/**
 * @version V1.0
 * @Copyright 2021- csdn - Powered By 长沙研发中心
 * @author: zhzh
 * @date: 2022/7/13 10:49 AM
 */
public class TwoPointerTechnique {

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1215/
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tmpA = headA;
        int aCnt = 1;
        ListNode tmpB = headB;
        int bCnt = 1;
        while (tmpA.next != null) {
            tmpA = tmpA.next;
            aCnt++;
        }
        while (tmpB.next != null) {
            tmpB = tmpB.next;
            bCnt++;
        }
        int subCnt = Math.abs(aCnt - bCnt);
        tmpA = headA;
        tmpB = headB;
        if (aCnt > bCnt) {
            for (int i = 0; i < subCnt; i++) {
                tmpA = tmpA.next;
            }
        } else {
            for (int i = 0; i < subCnt; i++) {
                tmpB = tmpB.next;
            }
        }
        while (tmpA != null && tmpB != null) {
            if (tmpA == tmpB) {
                return tmpA;
            }
            tmpA = tmpA.next;
            tmpB = tmpB.next;
        }
        return null;
    }

    /**
     * https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1296/
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode tmp = head;
        int cnt = 1;
        while (tmp.next != null) {
            tmp = tmp.next;
            cnt++;
        }
        if (n > cnt) {
            return head;
        }


        int index = cnt - n;
        if (index == 0) {
            head = head.next;
        }

        tmp = head;
        while (tmp != null) {
            index--;
            if (index == 0) {
                tmp.next = tmp.next.next;
                continue;
            }
            tmp = tmp.next;
        }

        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode listNode = removeNthFromEnd(head, 5);
        System.out.println(listNode.val);
    }

}
